package com.zlsy.learning.leetcode.linkedlist.l141;

import com.zlsy.learning.leetcode.linkedlist.l234.ListNode;

import java.util.HashSet;

/**
 * @author zhouliang
 * @date 2020/8/5 17:31 链表中环的检测 - 最后一位没有指向NULL的就存在环
 */
public class HasCycle {

  /** * 哈希表 ： 时间复杂度O（n） 空间复杂度O（n） */
  public static boolean hasCycle(ListNode head) {
    HashSet<ListNode> listNodes = new HashSet<>();
    while (head != null) {
      if (listNodes.contains(head)) {
        // 存在环
        return true;
      } else {
        listNodes.add(head);
      }
      head = head.next;
    }
    // 遍历都找不到元素
    return false;
  }

  /** * 双指针 时间复杂度O（N）空间复杂度O（1） */
  public static boolean hasCycle1(ListNode head) {
    if (head == null || head.next == null) {
      return false;
    }
    ListNode fast = head.next;
    ListNode slow = head;
    while (slow != fast) {
      // 如果快指针能走到终点，说明不存在环
      if (fast == null || fast.next == null) {
        return false;
      }
      // 否则就继续走
      fast = fast.next.next;
      slow = slow.next;
    }
    // 如果fast和slow存在相等的节点那么就有
    return true;
  }

  public static void main(String[] args) {
    ListNode head = new ListNode(3);
    head.add(2);
    head.add(0);
    head.add(-4);
    boolean b = hasCycle(head);
    System.out.println(b);
  }
}
